The present invention relates to a process for transmitting information bits, in which a transmitter executes the following steps:
formation of a first binary matrix from the information bits to be transmitted; PA1 conversion of the first binary matrix into a second binary matrix by application of a systematic block code corresponding to the product of elementary systematic block codes; and PA1 transmission of the bits extracted from the second binary matrix towards a channel, PA1 and a receiver executes the following steps: PA1 determination of a number p of indexes for which the data vector components are the least reliable; PA1 construction of a number q of binary words to be decoded from the said p indexes and from the decision vector; PA1 obtaining q' code words on the basis of algebraic decodings of the decision vector and the q binary words to be decoded; PA1 selection, from the q' code words obtained, of that having the shortest euclidean distance with the data vector; PA1 calculation of a correction vector, each component W.sub.j of the correction vector being respectively calculated by determining an optional concurrent word having its j-th component different from that of the selected code word, applying the formula: ##EQU2## when a concurrent word has been determined, M.sup.d and M.sup.c respectively designating the euclidean distances, with respect to the data vector, of the selected code word and of the concurrent word, and C.sub.j.sup.d and R'.sub.j respectively designate the j-th components of the selected code word and of the data vector; PA1 means to form a first binary matrix from information bits to be transmitted; PA1 elementary coding means instructed to convert the first binary matrix into a second binary matrix by application of a systematic block code corresponding to the product of elementary systematic block codes; and PA1 means to transmit the bits extracted from the second binary matrix towards a channel, PA1 the coder also comprising programming means in order to determine, from a number X supplied to program the number of information bits to be included in each first matrix, X positions uniformly distributed according to each dimension of the first matrix, the means for creating the first matrix being designed to place bits of known values in the said X positions, the said bits of known values being located after systematic coding in determined positions of the second binary matrix and not being transmitted towards the channel. PA1 means for forming an input matrix from a signal received according to a transmission channel, the input matrix being composed by digital samples the signs of which represent respective initial estimations of bits of a binary matrix formed by a redundancy coder applying a systematic block code corresponding to the product of elementary systematic blocks and the absolute values of which respectively measure the confidences associated with the said initial estimations; and PA1 iterative decoding means instructed to decode the input matrix according to successive decoding cycles, each decoding cycle successively comprising steps for searching code words for each elementary block code used in the product code, PA1 in which, at each code word search step, the decoding means receive a data matrix and a decision matrix with binary components which, before the first search step, are respectively constituted by the input matrix and by a matrix the binary components of which correspond to the signs of the samples of the input matrix, and produce for the following search step a new decision matrix the binary components of which represent respective new estimations of the bits of the second binary matrix and a new data matrix the samples of which have absolute values which respectively measure the confidences associated with the said new estimations, the decoded information bits being extracted from the decision matrix produced during the last code word search step, PA1 and in which each code word search step includes a division of the data matrix received into data vectors each corresponding to a code word of the elementary code and a corresponding division of the decision matrix received into decision vectors and elementary decodings with soft decisions to respectively process at least certain data vector/decision vector pairs, PA1 the decoder further comprising programming means to determine, from a number X supplied to program the number of decoded information bits to be extracted from the decision matrix, X positions uniformly distributed according to each dimension of a non-redundant sub-matrix of the said binary matrix, the means for forming the input matrix being designed to place, in positions corresponding to the said X positions, digital samples of determined signs and the absolute values of which are representative of maximum confidence.
formation of an input matrix from a signal received according to the said channel, the input matrix being of the same size as the second binary matrix, and being comprised of digital samples the signs of which represent respective initial estimations of the bits in the second binary matrix and the absolute values of which respectively measure the confidences associated with the said initial estimations; and PA2 iterative decoding of the input matrix including a number m of decoding cycles, each decoding cycle successively comprising code word search steps for each elementary block code used in the product code, PA2 in which, at each code word search step, a data matrix and a decision matrix with binary components are received which, before the first search step for the iterative decoding, are respectively constituted by the input matrix and by the matrix the binary components of which correspond to the signs of the input matrix samples, and for the following search step a new decision matrix is produced, the binary components of which represent new respective estimations of the bits of the second binary matrix and a new data matrix the samples of which have absolute values which respectively measure confidences associated with the said new estimations, PA2 in which decoded information bits are extracted from the decision matrix produced during the last code word search step, PA2 and in which each code word search step includes a division of the data matrix received into data vectors each corresponding to a code word of the elementary code and a corresponding division of the decision matrix received into decision vectors and elementary decodings with soft decisions to respectively process at least certain data vector/decision vector pairs. PA2 obtaining the new decision vector taken as equal to the said selected code word; and PA2 calculation of the new data vector by adding the correction vector multiplied by a first confidence coefficient to the corresponding input vector extracted from the input matrix.
On the subject of digital transmission of information (speech, image, data, etc.), a distinction is usually made between source coding and channel coding. Source coding forms the binary representation of the signal to be transmitted. It is normally designed as a function of the nature of the signal to be transmitted. Much effort has been expended in recent years on the subject of source coding in order to reduce the digital rate, while preserving good transmission quality. However, these new source coding techniques require better protection of the bits against perturbations during the transmission. Moreover, the physical and economic limitations of high-frequency components (noise factor, power saturation), as well as regulations on the level of power allowed for transmission limit the range of digital transmission systems.
For this reason much work has been carried out on the subject of channel coding, in particular on the subject of block coding. This type of error-correcting coding consists in adding n-k redundancy bits to k information bits originating from the source coding, and in using these redundancy bits on reception in order to correct certain transmission errors. The ratio R=k/n is called the efficiency of the code, and the coding gain G is defined as the ratio, expressed in decibels, between the energies per information bit Eb which are necessary at the input of the receiver without coding and with coding in order to reach a given binary error rate (BER). A typical objective is to create coders and especially their associated decoders such that: (i) the coding gain G is as high as possible (G&gt;5 dB for BER=10.sup.-5), (ii) the code efficiency R is as high as possible (R&gt;0.6), and (iii) the complexity of the decoding is as low as possible.
The case of the storage of the digital information may be seen as a particular case of transmission, in which the propagation channel includes a memory where the information remains in more or less long-term storage, the transmitter and the receiver may be the same or not. It will thus be understood that, in general, the notions of channel coding and of associated decoding are applicable to the field of the storage of information in the same way as to transmission, the errors to be corrected then being those due to the reading or to the writing in the memory, to the alteration in the content of the memory or also to communications (remote or not) with the devices for reading and writing in the memory.
It is known to enhance the performances of error-correcting codes by using concatenation techniques. In particular, the technique of product codes, which is more particularly involved with the present invention, makes it possible, from two simple block codes (that is to say having a small minimum Hamming distance d) to obtain a code whose minimum Hamming distance is equal to the product of the Hamming distances of the elementary codes used (see S. M. Reddy: "On decoding iterated codes", IEEE Trans. on Information theory, Vol. IT-16, No. 5, September 1970, pages 624-627).
If a block code with parameters (n.sub.1,k.sub.1,d.sub.1) is designated by C.sub.1 and a block code with parameters (n.sub.2,k.sub.2,d.sub.2) is designated by C.sub.2, the application of the code which is the product of C.sub.1 with C.sub.2 consists in ordering the k.sub.1 .times.k.sub.2 successive information bits in a matrix, and in coding the k.sub.1 rows of the matrix by the code C.sub.2, then the n.sub.2 columns of the resultant matrix by the code C.sub.1. The parameters of the product code P are then given by (n=n.sub.1 .times.n.sub.2 ; k=k.sub.1 .times.k.sub.2 ; d=d.sub.1 .times.d.sub.2). The efficiency R of the code P is equal to R.sub.1 .times.R.sub.2. Decoding of the code P according to the maximum likelihood a posteriori (MLP) makes it possible to reach optimal performance. The maximum asymptotic coding gain can then be approximated by the relation G&lt;10 log.sub.10 (R.d).
The product code is thus very beneficial, but decoding according to the MLP is generally too complex, except in the case of short block codes.
In their article "Separable MAP filters for the decoding of product and concatenated codes", Proc. ICC' 93, Geneva, Pages 1740-1745, May 1993, J. Lodge et al. proposed an iterative decoding algorithm of the type indicated in the introduction, in which the row vectors and the column vectors extracted from the data matrix are decoded using Bahl's algorithm (see L. R. Bahl et al, "Optimal decoding of linear codes for minimizing symbol error rate", IEEE Trans. on Information Theory, Vol. IT-20, pages 248-287, March 1974) which estimates Log Likelihood Ratios (LLRs) for bits. Bahl's algorithm provides soft decisions expressed by the LLRs, allowing performances close to those of the MLP to be achieved. However, it makes use of a decoding trellis having a number of statuses which grows exponentially as a function of n-k. As a result, while the algorithm of Lodge et al. is suitable for short codes such as, for example, Hamming's code (16,11,3), it proves unusable in practice for codes with a high efficiency such as, for example, the BCH code (63,51,5).
Another process of the type indicated at the beginning was presented in European Patent Application No. 0 654 910, the contents of which are incorporated in the present description.
The latter process can be used to decode all the product codes which are built from codes in linear blocks and for which an algebraic decoder is available. The performances obtained with this process are near optimum (see R. Pyndiah et al.: "Near optimum decoding of product codes", Proc. IEEE GLOBECOM' 94 Conference, Vol. 1/3, November-December 1994, San Francisco, pages 339-343). In fact, it can be used to obtain, for a given product code and in four iterations, a BER equal to 10.sup.-5 for a signal-to-noise ratio in the region of 2.5 dB above the theoretical Shannon limit for the product code in question. Moreover, this process is far less complex and much more reliable than the solution proposed by Lodge et al. It is thus possible to decode very large product codes, with elementary code lengths n.sub.1, n.sub.2 of up to 256.
In considering the creation of a circuit suitable for carrying out iterative decoding of the type mentioned in the introduction, hereafter called block turbo-code circuit or BTC circuit (see O. Raoul et al., "Architecture and design of a turbodecoder circuit for product codes", Proc. GRETSI' 95 Conference, Vol. 2, September 1995, pages 981-984), it is apparent that the surface area of the circuit can be considerably reduced by using the same elementary decoder to carry out several iterations rather than cascading several elementary decoders. Depending on the envisaged application, the number of iterations will be a function of the elementary decoder's complexity. The less the elementary decoder is complex, the greater the number of iterations, hence the advantage of reducing the complexity of the elementary decoder.
For reasons of economy, it is desirable to have a programmable BTC circuit allowing processing of data blocks of differing sizes with a varying number of redundancy bits. It can thus be envisaged to use the same BTC circuit for different applications, which allows an appreciable saving in terms of development costs.
A principal aim of the present invention is to respond to this requirement by proposing a transmission process for information bits allowing the use of a programmable BTC circuit.